The present invention relates generally to data networks and more particularly to the design and management of such networks.
For the purposes of this specification the term data network is taken to include any network in which signals originate from a multiplicity of sources. These signals may be in a variety of formats other than the digital packet arrangements associated with local area networks, Internet and intranet applications and may also include telephone networks, cable TV, cellular and satellite communications.
Controlling congestion on high-speed networks is becoming increasingly difficult and expensive. In the case of the Internet, it would historically have been impossible to predict the impact that the provision of services, such as the World Wide Web (WWW) would have generated. The traffic explosion which is now apparent and the extraordinary demand for new services means that bandwidth optimisation is now imperative for any network operator. Asynchronous Transfer Mode (ATM) in which signals are broken up into small cells of uniform size to carry voice, data and video across a network through ATM switches is widely used and is particularly suited to the present invention. The ATM switches at each network node operate at great speed to read the address of an incoming cell and direct it to an appropriate destination. The ongoing challenge to the operators of such networks is the effective management of system resources particularly in light of the increasing number of xe2x80x9cbandwidth-hungryxe2x80x9d applications.
All networks including ATM networks are of their nature bandwidth limited to some level therefore when the network is asked to communicate a new signal or a set of signals it is essential to accurately determine whether the request can be reliably processed without overloading the capacity of the network.
In connection oriented networks, this determination is sometimes referred to as connection admission control (CAC), and relies on knowledge about the behaviour of both the current signals on the network and of the new signal or signals. When a request is received for a new traffic stream to enter a network, the network will attempt to route that stream through a sequence of switches similar to the ATM switches already mentioned. There may be several different possible routes through the network and the network may have a means of choosing from among them. However, for transmission failure intolerant or time dependent networks a new stream can be handled along a particular route if and only if the sum of resource requirements, that is the current and new, at each switching point along the route does not exceed that switching point available resources. Thus, the present invention may be applied independently at each switching point in the network to determine whether resources will be exceeded at that point if the new stream is accepted.
The subsequent description will refer to connection admission at a particular point in the network.
The first known way of determining whether a new traffic stream can be handled by a network carrying existing traffic streams is to determine the peak resource requirement of each traffic stream. Then, the current capacity of the network used by the existing streams is represented by the sum of their peak requirements, and a new traffic stream can be handled by the network if its peak requirement plus the sum of the peak requirements of the existing streams does not exceed the maximum capacity of the network. This approach to connection admission control is referred to as xe2x80x9callocation on peakxe2x80x9d.
In networks where the peak requirement is its usual requirement, this is a simple and efficient method. For example, in a digital telephone network, the peak requirement of a call corresponds its usual requirement so that connection admission control is relatively straight forward. However, in situations where the requirements of a traffic stream vary during the time that stream is being carried by the network, then the method of allocation on peak is potentially wasteful. If, in practice, only a small number of the existing traffic streams are at their peak requirements, there will be a difference between the sum of the peak requirements and the actual capacity of the network used by the traffic streams at any particular time. If allocation on peak was then used as the connection admission control, the control system may prevent a particular signal being handled by the network, when, in fact, the network had sufficient capacity to handle that signal.
Therefore, techniques have been developed which take into account statistical variation of each of the traffic stream, to determine network demands associated with existing traffic streams. The bandwidth requirement per source can be greatly reduced by mixing traffic from many sources. The likelihood of peak demand from all traffic sources occurring simultaneously is small therefore using statistical multiplexing it is possible increase the number of signals which may be carried by the network.
Statistical multiplexing is made possible by the use of buffers in which cells can be stacked in queues, waiting to be processed by the switch. These buffers allow xe2x80x9csource modellingxe2x80x9d, to be implemented. This source modelling requires a statistical model to be derived from each carried traffic stream to obtain the statistical properties of the traffic streams as a whole. Each statistical model is a mathematical model containing a number of adjustable parameters. The model is then fitted to a respective stream by observing the traffic over a period of time as it passes through the buffers, deducing its statistical properties, and adjusting the parameters of the model to reproduce these. There is an obvious risk that buffers will occasionally overflow, leading to cell-loss, or that long queues will build up, causing unacceptably long transmission delays and the goal is to achieve the gain from statistical multiplexing while avoiding the consequences of congestion.
Where the behaviour of a traffic stream is easily captured by such a model, and where the number of different traffic streams is limited, this source modelling approach may prove satisfactory.
However, in situations where it is difficult to model the behaviour of a traffic stream, or when the number of different types of traffic streams is high, the derivation of appropriate models is computationally demanding. Thus, parametric modelling is unsatisfactory because of the wide variety of traffic types offered to the network, the difficulties in modelling burstiness and the time required to fit parameters. For example, multimedia sources require highly complex models to capture their statistical properties. In situations where the number of source or traffic stream types is large and where sources may adjust their behaviour in response to user input, or network conditions, source modelling does not work satisfactorily.
There is therefore a need for a network which will overcome the aforementioned problems.
Accordingly there is provided a data network of the type having at least one network switch, the network switch incorporating means for receiving data from more than one network source and means for onward transmission of said data characterised in that the network switch further incorporates means for processing and analysing data from each network source and abstracting a data characteristic from the analysed data.
Preferably the switch incorporates means for receiving a new data processing request from the network source.
Preferably the means for receiving the new data processing request incorporates means for processing, analysing and deriving a data model from the data processing request.
Ideally the switch includes a decision manager, the decision manager comprising:
means for determining a maximum allowable switch throughput parameter;
an integration device for combining the data model and the data characteristic to produce a switch throughput indicator; and
a comparator for comparing the switch throughput indicator and the maximum switch throughput parameter.
In one arrangement the decision manager incorporates:
a real time processor for comparing the comparator output and the data model with a pre-defined acceptance table to define a request response; and
means for transmitting the request response to the network source.
Preferably the means for abstracting the data characteristic incorporates a measurement apparatus having means for approaching a scaled cumulant generating function.
Preferably the measurement apparatus is an in-line device.
In a preferred arrangement the in-line device operates in real time and uses random blocks of time for approximating the scaled cumulant generating function.
Preferably the in-line device incorporates a throughput buffer.
Preferably the measurement apparatus further includes an estimator for analysing the new data processing request using an estimating operation to estimate the data model.
Ideally the estimator incorporates means for approximating a scaled cumulant generating function.
Preferably the modelling apparatus is an in-line device.
In a preferred arrangement the in-line device operates in real time and uses random blocks of time for the scaled cumulant generating function.
Preferably the in-line device is provided by a modelling buffer.
Preferably the network switch incorporates a revision processor for periodically refreshing the data characteristic.
Preferably the revision processor is connected to the decision manager for receiving the request response.
Preferably the network comprises a plurality of interconnected switches linking the network source to a network target.
Preferably each network switch between the network source and the network target incorporates means for generating and communicating a request response to the network source in response to a network target access request from the network source.
Preferably the switch is a gateway switch for communication with another network.
According to one aspect of the invention there is provided a data network of the type having at least one network switch, the network switch incorporating means for estimating a current resource demand requirement of network traffic in a queue, said means operating in line between a switch input and a switch output and incorporating means for approximating a scaled cumulant generating function to estimate the resource demand requirement.
Preferably the estimation of the scaled cumulant generating function is achieved using an arbitrary sequence of random times of network traffic in the queue.
Preferably the measured estimation of the scaled cumulant generating function is achieved using a random series of data blocks from the queue.
Preferably the data characteristic is abstracted according to
{circumflex over (xcex4)}(s)=max{xcex8:{circumflex over (xcex)}(T)(xcex8)xe2x89xa60}
Preferably the switch incorporates means for receiving a data processing request said means having a parametric estimator for identifying the data model for the data processing request.
According to another aspect of the invention there is provided a data network of the type having at least one network switch incorporating means for estimating a current source demand requirement of network traffic in a queue comprising means for generating an initial polygonal approximation and means for iteratively refining said polygonal approximation to a scaled cumulative generating function in response to sampled data.
Preferably the initial polygonal approximation is generated from declared parameters.
According to another aspect of the invention there is provided a data network performance management system for managing communications in a network comprising
means for receiving data from a network source on the network;
means for onward transmission of the data to the other network;
means for processing, analysing and abstracting a data characteristic from the data;
a decision manager, the decision manager comprising:
means for determining a maximum switch throughput parameter;
an integration device for combining the data model and the data characteristic to produce a switch throughput indicator and
a comparator for comparing the switch throughput indicator and the maximum switch throughput parameter;
a real time processor for comparing the comparator output and the data model with a pre-defined acceptance table; and
means for transmitting a request response to the network source.
Preferably the network performance management system as claimed in claim 26 wherein the means for processing, analysing and abstracting a data characteristic from the data incorporates:
means for approximating a polygonal approximation; and
means for iteratively refining said polygonal approximation to a scaled cumulative generating function in response to analysed data.
According to another aspect of the invention there is provided a method for managing the performance of a data network comprising the steps of:
processing, analysing and abstracting a data characteristic for data passing through a switch node of the data network;
receiving a data processing request from a network source;
processing, analysing and deriving a data model from the data processing request;
combining the data model and the data characteristic to produce a switch throughput indicator,
identifying a maximum allowable switch throughput parameter;
comparing the switch throughput parameter and the switch throughput indicator to produce a request response; and
communicating the request response to the network source.
Preferably the method further comprises the steps of:
accepting a data request from a network source; and
generating a new data characteristic.
Ideally the step of processing, analysing and abstracting the data characteristic comprises the steps of:
generating a polygonal approximation;
isolating a segment of data passing through the switch node; and
iteratively analysing a random series of blocks of the data for refining the polygonal approximation to a scaled cumulative generating function.
Preferably the blocks are analysed using an arbitrary sequence of random times.
Therefore, the present invention seeks to provide a method of connection admission control (CAC) which permits more complex systems to be handled than the known arrangements. At its most general, the present invention proposes that an estimate is made of the demand on the system from the current traffic stream, based on estimation functions, determined in real time using on-line measurement. An estimate is also made of the requirement of a new traffic stream, based on a readily available parameter of that traffic stream, and the results of the two estimates used to determine whether the new traffic stream can be handled by the network. If the likelihood of the network being unable to handle all the traffic streams is low enough, the stream is accepted. Once the new stream has been admitted to the network, the on-line measurement of the existing streams then takes into account the new stream in any subsequent processing.
Normally, a network has a plurality of interconnected switching points, and each switching point will usually have a processing function associated with that switching point. Therefore, the present invention is normally applied to each switching point, so that for each switching point an estimate is made of the demand on the system from the current traffic stream at that switching point and also an estimate is made of the requirement of a new traffic stream at that switching point. The result of the two estimates are then used at the switching point to determine whether the new traffic stream can be handled by the switching point, or not.
Usually, a signal to be handled by the network will pass from the origin of that signal to its destination via a plurality of switching points. In such a situation, it is preferable for the connection admission control of the present invention to be applied at each switching point and the signal passed from its source to its destination only if it is determined that the network is able to handle all the traffic streams, including the new one, at all switching points.
The present invention is not limited to arrangements in which demands on the system is determined at each switching point. An alternative is to provide measurement devices connected to the transmission links of the network, which monitor signals on the corresponding transmission links of the network and control the signals of that transmission link, either directly or by passing information to agents elsewhere in the network which control the signals of that transmission link, on the basis of the connection admission control of the present invention.